 
 struct ListNode {
      int val;
     ListNode *next;
     ListNode(int x) : val(x), next(nullptr) {}
 };

class Solution {

    public:
     ListNode * mergeTwoLists(ListNode * list1, ListNode * list2) {

             ListNode * head = new ListNode(0); // 创建一个头节点
            
            ListNode * sign = head ;

            list1 = list1->next; // 获取链表一的第一个结点
            list2 = list2->next; // 获取链表二的以一个结点

            while (list1 != nullptr && list2 != nullptr){
                
                // 如果值大的话，那么就创建个结点，把值大的存起来,小于的就放到后面，逐个结点比较2个链表
                if(list1->val >= list2->val){
                    head->next = new ListNode(0);
                    head = head->next;
                     head->val = list1->val;
                     list1 = list1->next ;
                }else if(list1->val < list2->val){
                    head->next = new ListNode(0);
                    head = head->next;
                    head->val = list2->val;
                    list2 = list2->next ;
                }
            }
          
          //如果list1还有剩余，把list剩余的结点保存起来
            while(list1 != nullptr){
                head->next = new ListNode(0);
                head = head->next;
                head->val = list1->val;
                list1 = list1->next;
         }

        // 如果list2还有剩余，把list2剩余的结点保存起来
            while(list2 != nullptr){
                head->next = new ListNode(0);
                head = head->next;
                head->val = list2->val;
                list2 = list2->next ;
        }
            return sign ;  // 把归并后的链表的头结点返回出去
    }
};